---
title: "L2-031 深入虎穴"
created: 2025-11-28
tags:
  - 算法
---

# L2-031 深入虎穴

## 题目 [L2-031 深入虎穴](https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?problemSetProblemId=1111914599412858888&page=1)

![[image-d8d51758.png]]

## 思路分析

找到唯一一个没有通向的门 为入口

从入口dfs 找到最远的门

## 代码实现

```cpp
#include <bits/stdc++.h>

using namespace std;

#define endl '\n'

#define int long long

using ll = long long;

using ull = unsigned long long;

using PII = pair<int, int>;

using Pll = pair<ll, ll>;

int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };

const int inf = 0x3f3f3f3f;

vector<vector<int>> g;

vector<int> visited;

int maxDeep=-inf;

int ans;

void dfs(int cur,int deep){

	if(deep>maxDeep){

		maxDeep=deep;

		ans=cur;

	}

	for(int nx:g[cur]){

		if(visited[nx])	continue;

		visited[nx]=true;

		dfs(nx,deep+1);

		visited[nx]=false;

	}

}

signed main() {

    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int n;cin>>n;

    g.resize(n+1);

    visited.resize(n+1,false);

    vector<bool> isStart(n+1,true);

	for(int i=1;i<=n;i++){

		int k;cin>>k;

		while(k--){

			int to;cin>>to;

			isStart[to]=false;

			g[i].push_back(to);

		}

	}

	int start;

	for(int i=1;i<=n;i++){

		if(isStart[i]){

			start=i;

			break;

		}

	}

//	cout<<start;

	visited[start]=true;

	dfs(start,0);

	cout<<ans;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[L2-030 冰岛人|L2-030 冰岛人]] 🏠 [[00-天梯赛]] ➡️ [[L2-032 彩虹瓶|L2-032 彩虹瓶]]